1. Field of the Invention
The present invention relates generally to methods and devices for inserting and authenticating a digital signature in digital data and, more particularly, encoders and decoders for inserting and authenticating a digital signature and associated data in digital image, video, and audio data.
2. Prior Art
Photographs, music and video are increasingly being digitally represented. There are a variety of reasons for this, including improved image or audio quality and more economic distribution capabilities. However, digital data content owners (hereinafter “content owners”) are increasingly aware of the associated risks of piracy and considerable effort has been directed towards minimizing this risk. Digital watermarking is one tool that has received attention for minimizing these risks. An early focus was on the design of watermarks that were not perceptible yet survived many forms of common signal processing such as MPEG-2 or JPEG-compression.
It is known in the art that there is also a need for fragile watermarks, e.g. watermarks that do not survive simple image processing operations. The purpose of these fragile watermarks is to provide a viewer with an indication of whether an image has been tampered with. The integrity of digital images is increasingly of concern since many low cost software systems allow very sophisticated image editing capabilities that can seamlessly alter an image. Currently, photographs are considered excellent evidence to support descriptions of events. However, this may change, if widespread “doctoring” of images leads the general public to become suspicious of the authenticity of an image.
These issues have also been addressed in the art. The solution has been one based on classical cryptography within which authentication is well understood. The basic idea behind cryptographic authentication is to pass the data through a one-way hash function resulting in an N-bit hash. The N-bit hash is then encrypted using the private key of a public key encryption algorithm to form a digital signature. To authenticate the data, the data in question is once again hashed and this N-bit sequence is compared with the digital signature that is decrypted using the associated public key.
A disadvantage of the system as it was originally proposed for a image data was the need for two files, one containing the image and the other containing the signature. Authentication requires the presence of both files, which can be a nuisance since it is very easy, for example, to transmit an image but forget to transmit the associated signature. Ideally, a single file would suffice. An obvious solution would be to concatenate the signature into the header of the image file format. However, this solution is problematic when images are converted between various file formats, e.g. tiff, bmp, etc.
Recently, Wong [P. H. Wong, “A Public Key Watermark for Image Verification and Authentication”, Int. Conf. On Image Processing, 455–459, October 1998] proposed a straightforward way to insert a function of the signature into the image itself. Such a system has the advantage of being unaffected by changes in image file formats and does not need any form of meta-data. Authentication is performed on independent blocks of the image. For each block, Xr, the least significant bit of each pixel is set to zero. This modified block is then passed through a hash function, together with the original image width and height information. The output of this hash function is then exclusive OR'ed (XOR'ed) with a corresponding set of bits, Br to form a signature, Wr which is public key encrypted such that Cr=EK, (Wr) and Cr is inserted into the least significant bit (LSB) of the block to form a watermarked image block Yr. Wong teaches that Br is a binary image or pattern whose dimensions must be less than or equal to the length of the hash. The purpose of the XOR is to scramble the binary image, Br. Subsequently, at decoding, the LSB plane of each block is decrypted using the associated public key and it is XOR'ed with the hash of the block after setting the least significant bits of the block to zero. If the block is authentic, i.e. unchanged, then the result is once again Br, i.e., XORing a second time with the same hash value unscrambles the pattern Br. Otherwise, the pattern remains scrambled. Authentication of the image is performed by visual inspection of the patterns, B′r, though in practice, a computer could perform a bit-wise comparison of Br and B′r. Strictly, such a scheme only authenticates the most significant bits of each pixel since the LSB is altered so as to carry the corresponding encrypted signature.
Others in the art have described situations in which rightful ownership could not be resolved by a straightforward application of watermarking. In particular, they identified a situation in which anyone could claim ownership of a watermarked image through a process whereby a counterfeit watermark is inserted. They proposed a solution to this problem using a method called “non-invertible” watermarking. The basic idea behind this method is to construct a watermark based on a non-invertible function of the original image. An example of a non-invertible function is a one-way hash function commonly used in cryptography. Such a function takes a string of bits as input and outputs a finite, for example, a 1000-bit output. However, given the 1000-bit output, it is computationally infeasible to determine the corresponding input. It should be noted that such a watermark can only be read by the content owner or someone in possession of the original image or its hashed key. Thus, a public watermark, i.e. a watermark that can be read by anyone, cannot be non-invertible or, at least, the benefits of non-invertibility are lost since all readers must have knowledge of the hashed value.
Furthermore, authenticating an image that is to be subsequently compressed and later decompressed is troublesome with the methods and devices of the prior art. Many in the art have looked at this problem from the perspective of authentication schemes that survive JPEG compression. That is, while the digital data has been altered by the lossy compression, the image is essentially the same.